//
// Description: 701. 二叉搜索树中的插入操作
// Created by Loading on 2022/2/26.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>
#include <Utils.h>

using namespace std;

/* 迭代 */
TreeNode *insertIntoBST(TreeNode *root, int val) {
    if (!root) {
        return new TreeNode(val);
    }

    auto tmp = root;
    while (tmp) {
        if (val > tmp->val) {
            if (!tmp->right) {
                tmp->right = new TreeNode(val);
                break;
            } else {
                tmp = tmp->right;
            }
        } else {
            if (!tmp->left) {
                tmp->left = new TreeNode(val);
                break;
            } else {
                tmp = tmp->left;
            }
        }
    }

    return root;
}

/* 递归 */
TreeNode *insertIntoBST_Recursion(TreeNode *root, int val) {
    if (!root) {
        return new TreeNode(val);
    }

    if (val > root->val) {
        root->right = insertIntoBST_Recursion(root->right, val);
    } else {
        root->left = insertIntoBST_Recursion(root->left, val);
    }

    return root;
}

int main() {
    vector<int> nums = {40, 20, 60, 10, 30, 50, 70};
    auto root = generateTreeNode(nums);
    int val = 25;
    // 迭代
    root = insertIntoBST(root, val);
    // 递归
//    root = insertIntoBST_Recursion(root, val);
    string res = printfTreeNodeOfLevel(root);
    cout << res << endl;

    return 0;
}